package leetcode.N101_N200;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/18 11:28 上午
 */
public class N134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int lengthG = gas.length;
        int lengthC = cost.length;
        if (lengthG == 0 || lengthC != lengthG) {
            // 非法输入
            return -1;
        }
        for (int i = 0; i < lengthC; i++) {
            int currentGas = gas[i];
            int currentCost = cost[i];

            if (currentGas < currentCost) {
                // 当前节点的汽油不能到达下一节点  当前节点不能作为起点
                continue;
            }
            // 以当前节点作为起点 开始往后走
            int nextIndex = go(i, lengthC, gas, cost);
            if (nextIndex == i || nextIndex == -1) {
                // 返回的解  或者 无解
                return nextIndex;
            } else {
                // 跳过无效节点
                i = nextIndex;
            }
        }
        return -1;
    }

    private int go(int start, int length, int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;

        for (int i = start; i < length; i++) {
            totalCost += cost[i];
            totalGas += gas[i];
            if (totalCost > totalGas) {
                // 从本次起点出发 无法到达i+1处
                // 那么无论从当前起点start到当前点i之间的任何节点出发  都无法到达i+1节点，所以下一轮可以从i+1节点开始找起点
                return i;
            }
        }
        for (int i = 0; i < start; i++) {
            totalCost += cost[i];
            totalGas += gas[i];
            if (totalCost > totalGas) {
                // 无法到达下一节点 可断定 无法形成环
                return -1;
            }
        }
        // 可以回到起点 则返回起点位置
        return start;
    }



}
